package DoblePointer;//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 10⁵ 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1404 👎 0


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class minWindow {
    public String minWindow(String s, String t) {
        int lens = s.length();
        int lent = t.length();
        //对t的字符进行计数
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0;i<lent;i++){
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i),0)+1);
        }
        int min = lens+1;  //最小长度
        int start=0, end=lens-1 ; //记录起始位置
        //然后s滑动窗口使得t的计数为0;
        for(int i=0,j=0;j<lens;j++){
            char c = s.charAt(j);  //当前字符
            //当前字符在计数中
            if(map.containsKey(c)){
                map.put(c,map.get(c)-1);  //对应字符计数减1
            }
            //如果当前满足覆盖,则缩减窗口，否则继续移动右边界
            if(isContains(map)){
                //缩小窗口直到不满足
                while(isContains(map)){
                    char ct = s.charAt(i);  //左边界字符
                    if(map.containsKey(ct)){
                        map.put(ct, map.get(ct)+1);   //回补左边界字符
                    }
                    i++;
                }
                //因为i多移动了一位才不满足，记录原来满足的长度
                if(j-(i-1)+1 < min ){
                    start = i-1;
                    end = j;
                    min = j-(i-1)+1;
                }
            }
        }
        if(min == lens+1){
            return "";
        }else{
            return s.substring(start,end+1);
        }

    }

    //判断是否当前窗口已经全覆盖了,即计数不能为大于0
    private boolean isContains(HashMap<Character,Integer> map){
        for(Map.Entry<Character,Integer> entry : map.entrySet()){
            if(entry.getValue()>0){
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
